{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Damgard-Jurik Scheme of Paillier\n", "================" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Generalisation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The publickey cryptosystem uses computations modulo $n^{s+1}$ where $n$ is an $RSA$ modulus and $s$ is a natural number. It contains **Paillier's scheme** as a special case by setting $s=1$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We start from the observation that if $n=pq,p,q$ odd primes, then $Z^*_{n^{s+1}}$ as a multiplicative group is a direct product $G\\times H$, where $G$ ic cyclic of order $n^s$ and $H$ is isomorphic to $Z^*_{n}$, which follows directly from elementary number theory.\n", "\n", "Thus, the factor group $\\bar{G}=Z*_{n^{s+1}}/H$ is also cyclic of order $n^s$. For an arbitary element $a \\in Z_n^{s+1}$, we let $\\bar{a} H$ we denote the element represented by $a$ in the factor group $\\bar{G}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Lemma 1: For any $s< p, q$, the element $n+1$ has order $n^s$ in $Z_n^{s+1}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is easy to compute $i$ from $(1+n)^i \\mod n^{s+1}$. If we define the function $L()$ by $L(b)=(b-1)/n$ then clealy we have:\n", "\n", "$$\n", "L((1+n)^i \\mod n^{s+1}) =(1 + \\binom i 2 n + \\cdots + \\binom i s n ^{s-1} ) \\mod n ^s\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Key Generation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On input the security parameter $k$, choose an $RSA$ modulus $n=pq$ of length $k$ bits. Also choose an element $g\\in Z_n^{s+1}$ such that $g=(1+n)^j x$ mod $n^{s+1}$ for a known $j$ relatively prime to $n$ and $x \\in H$.\n", "\n", "This can be done, $e.g$, by choosing $j, x$ as random first and computing $g$;\n", "\n", "Let $\\lambda$ be the $lcm$ of $p-1$ and $q-1$. By the Chinese Remainder Theorem, choose $d$ such that $d$ mod $n\\in Z_n$ and $d=0$ mod $\\lambda$. \n", "\n", "$$\n", "d \\equiv \\left\\{\n", "\\begin{aligned}\n", "0 &\\mod \\phi(N) \\\\\n", "Z_n &\\mod N\n", "\\end{aligned}\n", "\\right\\}\n", "$$\n", "\n", "\n", "Any such choice of $d$ will work in the following.\n", "\n", "Now the pubkey is $n, g$ while the secret key is $d$." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from klefki.types.algebra.meta import field\n", "from klefki.types.algebra.utils import randfield\n", "from klefki.numbers.primes import generate_prime\n", "from klefki.crypto.damgard_jurik import damgard_jurik_reduce\n", "from klefki.numbers import lcm\n", "from random import randint\n", "from math import gcd" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "k = 256\n", "\n", "p, q = generate_prime(k), generate_prime(k)\n", "assert p != q\n", "\n", "# Paillier's scheme is a special case by setting s=1\n", "s = 3\n", "n = p * q\n", "\n", "lam = lcm((p - 1), (q - 1))\n", "assert gcd(n, lam) == 1\n", "\n", "G = field(n**s, \"G\") # n ** s == n if s = 1\n", "# multiplicative group\n", "MG = field(n ** (s+1), \"N^{s+1}\") # n ** (s +1 ) == n2 in pailer case\n", "H = field(n, \"H\")\n", "LG = field(lam, \"LCMGroup\")" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "j = generate_prime(k)\n", "assert gcd(j, n) == 1\n", "\n", "x = randfield(H)\n", "g = MG((MG(1 + n) ** j) * x)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "from klefki.numbers import crt" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "# Find d such that d = 0 mod lambda and d = 1 mod n^s\n", "d = crt(a_list=[0, 1], n_list=[LG.P, G.P])\n", "assert d % G.P == 1\n", "assert d % LG.P == 0" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "pubkey = (n, g)\n", "privkey = d" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Encryption" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The paintext set is $Z_{n^s}$. Given a paintext $i$, choose a random $r \\leftarrow Z^*_{n^{s+1}}$, and lte the cipertext be $E(i, r) = g^ir^{n^s} \\mod n^{s+1}$" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "r = randfield(MG)\n", "i = 31415926\n", "\n", "def encrypt(i, r):\n", " return g ** i * r ** (n**s)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "c = encrypt(i, r)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Decryption" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Given a ciphertext $c$, first compute $c^d \\mod n^{s+1}$, Clearly, if $c=E(v, r)$, we get\n", "\n", "\\begin{align}\n", "c^d &= (g^i r^{n^s})^d\\\\\n", "&=((1+n)^{ij} x^i r^{n^s})^d\\\\\n", "&=(1+n)^{jid}(x^ir^{n^s})^d \\\\\n", "&=(1+n)^{jid \\mod n^s}(x^ir^{n^s})^{d \\mod \\lambda}\\\\\n", "&=(1+n)^{jid \\mod n^s}\n", "\\end{align}\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", "g^d &= ((1 + n)^jx)^d \\\\\n", "&=(1 + n)^{jd} x^d \\\\\n", "&=(1+n)^{jd \\mod n^2}x^{d \\mod \\lambda}\n", "\\end{align}" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c ** d == (g ** i * r ** (n**s))**d \\\n", " == (MG((MG(1 + n) ** j) * x) ** i * r ** (n**s)) ** d \\\n", " == (MG(MG(1 + n) ** (j*i)) * (MG(x) ** i) * r ** (n**s)) ** d \\\n", " == MG(MG(1 + n) ** (j * i * d)) * (((MG(x) ** i) * r ** (n**s)) ** d)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(((MG(x) ** i) * r ** (n**s)) ** LG(d)).value == 1" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "G::31415926" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "G(damgard_jurik_reduce((c ** d).value, n, s)) * ~G(damgard_jurik_reduce((g ** d).value, n, s))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A Threshold Variant of Paillier" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can solve our problem by letting the servers help us compute $E(i, r)^d \\mod n^{s+1}$. Then if we use $g = n + 1$ and choose d such that $d = 1 mod n^s$ and $d = 0 \\mod \\lambda$, the remaining part of the decryption is easy to do without knowledge of $d$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Key generation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We find 2 primes $p$ and $q$, that satisifies $p = 2p' + 1$ and $q = 2q' + 1$, where $p'$ and $q'$ are primes and different from $p,q$. \n", "\n", "We set $n = pq$ and $m = p'q'$,we decide some $s>0$, thus the paintext space will be $Z_{n^s}$.\n", "\n", "We pick $d$ to satisfy:\n", "\n", "$$\n", "d \\equiv \\left\\{\n", "\\begin{aligned}\n", "0 &\\mod m \\\\\n", "1 &\\mod n^s\n", "\\end{aligned}\n", "\\right\\}\n", "$$\n", "\n", "And share $d$ with $SSSS$ in $Z_{n^sm}$, the secret share of the i'th authority will be $s_i=f(i)$ for $1 \\le i \\le l$, and the pubkey will be $n$." ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "from klefki.crypto.ssss import SSSS" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "k = 256\n", "\n", "p_, q_ = generate_prime(k), generate_prime(k)\n", "assert p != q" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [], "source": [ "p, q = (p - 1) // 2, (q - 1) // 2" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "n = p * q\n", "m = p_ * q_" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "G = field(n**s, \"G\") # n ** s == n if s = 1\n", "# multiplicative group\n", "MG = field(n ** (s+1), \"N^{s+1}\") # n ** (s +1 ) == n2 in pailer case\n", "H = field(n, \"H\")\n", "LG = field(m, \"MGroup\")" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "j = generate_prime(k)\n", "assert gcd(j, n) == 1\n", "x = randfield(H)\n", "g = MG((MG(1 + n) ** j) * x)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [], "source": [ "d = crt(a_list=[0, 1], n_list=[m, n])" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [], "source": [ "F = field(n**s * m, \"n^sm\")" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [], "source": [ "ssss = SSSS(F)" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [], "source": [ "k = 3\n", "l = n = 6" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ssss.setup(d, k, n)" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [], "source": [ "shares = [ssss.join(i) for i in range(1, n)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Encryption" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [], "source": [ "def encrypt(i, r):\n", " return g ** m * r ** (n**s)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [], "source": [ "r = randfield(MG)\n", "i = 31415926\n" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [], "source": [ "c = encrypt(i, r)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Share decryption" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The i’th authority will compute $c_i = c^{2 \\Delta s_i}$, where $c$ is the ciphertext, $\\Delta = l!$\n", "\n", "If we have the required k (or more) number of shares with a correct proof, we can combine them into the result by taking a subset S of k shares and combine them to" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "c' = \\prod_{i\\in S} c_i^{2\\lambda_{0,i}^S} \\\\\n", "$$\n", "\n", "Where:\n", "\n", "$$\n", "\\lambda_{0,i}^s=\\Delta \\prod_{i' \\in S;i} \\frac{-i}{i-i'} \\in Z\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implementation" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "from klefki.crypto.damgard_jurik import DJPaillier\n", "from klefki.numbers.primes import generate_prime\n" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "P, Q = generate_prime(256), generate_prime(256)\n", "s = 3" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [], "source": [ "m = 42" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "djp = DJPaillier(P, Q, s)" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "djp.D(djp.E(m)).value == m" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Threshold Version" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Note that the threshold DJP is imported via https://github.com/cryptovoting/damgard-jurik" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "from klefki.crypto.damgard_jurik import ts_dj\n", "\n", "public_key, private_key_ring = ts_dj.keygen(\n", " n_bits=512,\n", " s=3,\n", " threshold=100,\n", " n_shares=300\n", ")" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[mpz(124),\n", " mpz(186),\n", " mpz(54),\n", " mpz(239),\n", " mpz(252),\n", " mpz(269),\n", " mpz(136),\n", " mpz(221),\n", " mpz(109),\n", " mpz(29),\n", " mpz(74),\n", " mpz(212),\n", " mpz(90),\n", " mpz(259),\n", " mpz(13),\n", " mpz(172),\n", " mpz(231),\n", " mpz(32),\n", " mpz(43),\n", " mpz(194),\n", " mpz(53),\n", " mpz(3),\n", " mpz(176),\n", " mpz(246),\n", " mpz(300),\n", " mpz(37),\n", " mpz(14),\n", " mpz(190),\n", " mpz(125),\n", " mpz(208),\n", " mpz(233),\n", " mpz(297),\n", " mpz(42),\n", " mpz(127),\n", " mpz(30),\n", " mpz(236),\n", " mpz(188),\n", " mpz(290),\n", " mpz(248),\n", " mpz(81),\n", " mpz(211),\n", " mpz(95),\n", " mpz(143),\n", " mpz(187),\n", " mpz(170),\n", " mpz(46),\n", " mpz(110),\n", " mpz(8),\n", " mpz(112),\n", " mpz(150),\n", " mpz(68),\n", " mpz(52),\n", " mpz(79),\n", " mpz(12),\n", " mpz(126),\n", " mpz(103),\n", " mpz(86),\n", " mpz(139),\n", " mpz(93),\n", " mpz(135),\n", " mpz(134),\n", " mpz(18),\n", " mpz(223),\n", " mpz(262),\n", " mpz(104),\n", " mpz(218),\n", " mpz(60),\n", " mpz(10),\n", " mpz(131),\n", " mpz(162),\n", " mpz(261),\n", " mpz(267),\n", " mpz(284),\n", " mpz(44),\n", " mpz(140),\n", " mpz(65),\n", " mpz(33),\n", " mpz(204),\n", " mpz(230),\n", " mpz(282),\n", " mpz(39),\n", " mpz(58),\n", " mpz(4),\n", " mpz(203),\n", " mpz(27),\n", " mpz(88),\n", " mpz(106),\n", " mpz(242),\n", " mpz(67),\n", " mpz(210),\n", " mpz(50),\n", " mpz(111),\n", " mpz(173),\n", " mpz(180),\n", " mpz(219),\n", " mpz(59),\n", " mpz(107),\n", " mpz(289),\n", " mpz(57),\n", " mpz(174)]" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "private_key_ring.i_list" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "mpz(42)" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = 42\n", "c = public_key.encrypt(m)\n", "private_key_ring.decrypt(c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Ref:\n", " \n", "* I. Damg˚ard and M. Jurik. A generalisation, a simplification and some applications of paillier’s proba- bilistic public-key system. In Public Key Cryptography, pages 119–136, 2001.\n", " \n", " \n", "* Damgard-Jurik implementation https://github.com/cryptovoting/damgard-jurik" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.2" } }, "nbformat": 4, "nbformat_minor": 2 }